<?php

require_once 'util.php';
// Output all prime numbers up to a specified integer n.
//
// Solution:
// Interger n is a prime number if it is not divisible by any number other than 1 and itself.
// Assume n can be written by n=p1*m where m is not a prime number, then m can be written as m=p2*p3, then n=p1*p2*p3.
// Eventually, we don't have to test n against m.
//
// This gives my approach:
// n is a prime number if it is not divisible by the prime numbers smaller than it.
//
// Store a static prime number list
// 1) If the new number is less than the largets prime number,
// Just print the prime numbers smaller than the number;
// 2) If the new number is larger than the largets prime number,
// starting testing searching from primes.top()

// A global array can make function calls faster
$primes = array( 1 );

$array = getPrimeNumbersUpto( 50 );

echo implode(' ', $array);

function getPrimeNumbersUpto( $number ){
	global $primes;
	$count = count( $primes );
	$largest = $primes[ $count-1 ];

	$results = array();
	foreach( $primes as $prime ){
		if( $prime <= $number ){
			$results[] = $prime;
		}
	}

	if( $largest < $number ){
		for( $test=$largest + 1; $test<=$number; $test++ ){
			if( isPrime( $test, $primes ) ){
				$results[] = $test;
			}
		}
	}

	return $results;
}

// Test the new number against current primes, add to the list if is a prime
function isPrime( $number, &$primes ){
	$isPrime = true;
	foreach( $primes as $prime ){
		if( 0 == $number % $prime && $prime != 1 ){
			// Divisible! Not a prime
			$isPrime = false;
			break;
		}
	}

	if( $isPrime ){
		array_push( $primes, $number );
	}

	return $isPrime;
}
